package zuo.baseUP4_Tree;

import javax.sound.midi.Soundbank;
import java.util.List;

/**
 * @Author: Forx
 * @Data: 2021/6/18
 * @Desc: Algorithm - zuo.baseUP4_Tree
 * @Version: v1.0
 */
public class Main {
    /**
     *
     * 叉树节点间的最大距离问题
     * 从二叉树的节点a出发,可以向上或者向下走,但沿途的节点只能经过一次,到达节点b时路
     * 径上的节点个数叫作a到b的距离,那么二叉树任何两个节点之间都有距离,求整棵树上的最
     * 大距离。
     *
     * 分情况讨论:
     *  1.根不参与最大距离这条路
     *  2.根参与最大距离
     * */
    public static class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int data){
            this.val = data;
        }
    }
    public static class Info{
        public int maxDistance;
        public int height;

        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
    public static int getMaxDis(Node tree){
        return process(tree).maxDistance;
    }

    public static Info process(Node x){
        if(x == null)return new Info(0,0);
        Info left = process(x.left);
        Info right = process(x.right);
        int p1 = left.maxDistance;
        int p2 = right.maxDistance;
        int p3 = left.height + 1 + right.height;
        int max = Math.max(p3,Math.max(p2,p1));
        int height = Math.max(left.height,right.height)+1;
        return new Info(max,height);
    }

/**
 * 派对的最大快乐值
 * 员工信息的定义如下:
 * class Employee i
 * public int happy;:∥这名员工可以带来的快乐值
 * List< Employee> subordinates;∥这名员工有哪些直接下级
 * 公司的每个员工都符合 Employee类的描述。整个公司的人员结构可以看作是一棵标准的、没有环的
 * 多叉树。树的头节点是公司唯一的老板。除老板之外的每个员工都有唯一的直接上级。叶节点是没有
 * 任何下属的基层员工( subordinates列表为空),除基层员工外,每个员工都有一个或多个直接下级
 * 这个公司现在要办pay,你可以决定哪些员工来,哪些员工不来。但是要遵循如下规则。
 * 如果某个员工来了,那么这个员工的所有直接下级都不能来
 * 2.派对的整体快乐值是所有到场员工快乐值的累加
 * 3你的目标是让派对的整体快乐值尽量大
 * 给定一棵多叉树的头节点boss,请返回派对的最大快乐值。
 *
 * 对于节点X有以下几种情况
 * 1.X参与 即 X乐 + X_son1不来的乐 + X_son2不来的乐 ...
 * 2.X不参与 即 max(X_son2不来的乐,来的乐) + max(son2不来的乐,来的乐) ...
 *
 *
 * */
    public static class employee{
        public int happyVal;
        public List<employee> employees;

}
    public static class empInfo{
        public int comeHappy;
        public int notcomeHappy;

        public empInfo(int comeHappy, int notcomeHappy) {
            this.comeHappy = comeHappy;
            this.notcomeHappy = notcomeHappy;
        }
    }

    public static int getMaxHappy(employee boss){
        empInfo headInfo = process(boss);
        return Math.min(headInfo.comeHappy,headInfo.notcomeHappy);
    }

    public static empInfo process(employee x){
        if(x.employees.isEmpty())return new empInfo(x.happyVal,0);
        int come = x.happyVal;
        int notCome = 0;
        for(employee e:x.employees){
            empInfo nextInfo = process(e);
            come += nextInfo.notcomeHappy;
            notCome += Math.max(nextInfo.comeHappy,nextInfo.notcomeHappy);
        }
        return new empInfo(come,notCome);
    }
    /**
     *  Morris遍历
     * 一种遍历二叉树的方式，并且时间复杂度O(N),额外空间复杂度O(1)
     * 通过利用原树中大量空闲指针的方式，达到节省空间的目的
     *
     * Morris 遍历细节
     * 假设来到当前节点cur,开始时cur来到头节点位置
     * 1)如果cur没有左孩子，cur向右移动（cur=cur.right)
     * 2)如果cur有左孩子，找到左子树上最右的节点mostRight:
     *      a.如果mostRight的右指针指向空，让其指向cur,
     *          然后cur向左移动（cur=cur.left)
     *      b.如果mostRight的右指针指向cur,让其指向null,
     *          然后cur向右移动（cur=cur.right)
     * 3)cur为空时遍历停止
     * */
    public static void morris(Node root){
        if(root==null){
            return;
        }
        Node cur = root;
        Node mostRight = null;
        while (cur!=null){
            mostRight = cur.left;
            if(mostRight!=null){
                while (mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){
                    //System.out.println(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }

            }
            cur = cur.right;
        }
    }
    /**
     * 遍历两次的只打印第二次,遍历一次的直接打印
     * 只有有左子树的节点才会被遍历两次
     * */
    public static void morrisIn(Node root){
        if(root==null){
            return;
        }
        Node cur = root;
        Node mostRight = null;
        while (cur!=null){
            mostRight = cur.left;
            if(mostRight!=null){
                while (mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){

                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }

            }
            System.out.println(cur.val);
            cur = cur.right;
        }
    }

    /**
     * 遍历两次的只打印第一次,遍历一次的直接打印
     * 只有有左子树的节点才会被遍历两次
     * */

    public static void morrisPre(Node root){
        if(root==null){
            return;
        }
        Node cur = root;
        Node mostRight = null;
        while (cur!=null){
            mostRight = cur.left;
            if(mostRight!=null){
                while (mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){
                    System.out.println(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }

            }else {
                System.out.println(cur.val);
            }
            cur = cur.right;
        }
    }
    /**
     *
     * 只打印第二次遇见的左树右边界逆序
     * */
    public static void morrisPost(Node root){
        if(root==null){
            return;
        }
        Node cur = root;
        Node mostRight = null;
        while (cur!=null){
            mostRight = cur.left;
            if(mostRight!=null){
                while (mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){
                    //System.out.println(cur.val);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    printRightEdge(cur);
                    mostRight.right = null;
                }

            }
            cur = cur.right;
        }
        printRightEdge(root);
        System.out.println("");
    }



    /*
    * 右边界逆序打印
    * */
    public static void printRightEdge(Node x){
        Node tail = reverseEdge(x);
        Node cur = tail;
        while (cur!=null){
            System.out.println(cur.val);
            cur = cur.right;
        }
        reverseEdge(tail);
    }
    public static Node reverseEdge(Node from){
        Node pre = null;
        Node next = null;
        while (from!=null){
            next = from.right;
            from.right = pre;
            pre = from;
            from = next;
        }
        return pre;
    }



    public static boolean isBST(Node root){
        if(root==null){
            return true;
        }
        Node cur = root;
        Node mostRight = null;
        int preVal = Integer.MIN_VALUE;
        //int curVal =  Integer.MIN_VALUE;
        while (cur!=null){
            mostRight = cur.left;
            if(mostRight!=null){
                while (mostRight.right!=null && mostRight.right!=cur){
                    mostRight = mostRight.right;
                }
                if(mostRight.right==null){

                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                }else {
                    mostRight.right = null;
                }

            }
            if(cur.val <= preVal){
                return false;
            }
            preVal = cur.val;
            cur = cur.right;
        }
        return true;
    }
    /**
     *
     *
     * */


}
